The invention relates to a method of computing path metrics applied in a Viterbi detector and a related apparatus thereof, and more particularly, to a method of computing path metrics in a parallel processing manner and the related apparatus thereof.
In digital communication systems, the Maximum Likelihood Sequence Detection (MLSD) is a popular technique applied in numerous communication systems with different architectures. The Viterbi detector is a popular circuit utilizing the MLSD technique. As is well known in the art, Additive white Gaussian noise (AWGN) and many sources of interference exist in general communication channels. To reduce the error rate of signal detection, most communication systems encode the data and transmit the encoded data instead of transmitting the original data. The encoding procedure comprises convoluting the data according to a specific algorithm, where the number of bits of the encoded data is more than the original data. Before a receiver decodes the received data, the receiver determines the accuracy of the received data according to the specific algorithm. The specific algorithm is capable of restoring the incorrect received data.
Take the Viterbi Algorism (VA) as an example. Please refer to FIG. 1. FIG. 1 is a state diagram of the related art Viterbi Algorism having six states. As shown in FIG. 1, each state relates to a different input value (i.e., original data) and a corresponding output value (i.e., encoded signal), such as 6, 4, 2, 0, −2, −4, or −6. After the encoded signal is transmitted to the communication channel, the encoded signal may be affected by noise. Due to the encoded signal being disturbed, the signal receiver may determine the received encoded signal to be an incorrect value. For example, if an encoded signal equal to “6” is affected by interference, when the receiver receives the affected signal it will erroneously, the receiver determine the signal to be equal to “5”. As can be seen from referring to FIG. 1, it is obvious that no encoded signal is equal to “5”, therefore it is an incorrect signal. The receiver expects the encoded signal to be “6” or “4”, but still needs an algorithm to restore the received encoded signal value to the original encoded signal value transmitted by the transmitter.
Please refer to FIG. 2. FIG. 2 is a related art Trellis tree diagram with an operation timing. The Trellis tree is established according to the state diagram shown in FIG. 1. The Trellis tree includes a plurality of states S0, S1, S3, S4, S6, S7, and a plurality of branches 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 between states. Assuming the state S7 is the initial state, if a bit equal to “0” is received by the encoder, the encoder outputs a value equal to 4 and enters the state S6. Next, if a bit equal to “0” is received by the encoder, the encoder outputs a value “0” and enters the state S4. Additionally, the receiver restores the received signal to be a correct signal according to the Trellis tree. For example, assume the initial state is state S7 and the receiver receives an input signal equal to “2”. The receiver computes a plurality of branch costs according to the input signal and the ideal encoded signal (i.e., equal to “6”, “4” . . . etc). Next the receiver determines the correct value of the input signal through a plurality of path metrics P, generated according to the branch costs. Each path metric P is an accumulated result of a plurality of branch costs corresponding to different input timings. In practice, the branch costs are equal to the absolute value of the difference between the input signal and each ideal encoded signal. Hence, the operations of generating the path metrics of each state are represented by the following equations:PS7=min{(PS7+BS7->S7),(PS3+BS3->S7)}  Equation (1)PS6=min{(PS7+BS7->S6),(PS3+BS3->S6)}  Equation (2)PS4=PS6+BS6->S4  Equation (3)PS3=PS1+BS1->S3  Equation (4)PS1=min{(PS4+BS4->S1),(PS0+BS0->S1)}  Equation (5)PS0=min{(PS4+BS4->S0),(PS0+BS0->S0)}  Equation (6)
Since the operation of the Trellis tree diagram is well known to those skilled in the art, a detailed description is omitted for the sake of brevity. To explain entering the state Sj from the state Si in an operation timing, the state Si is called a previous state, and the state Sj is called a current state. In the next operation timing, the current state Sj becomes one of the previous states. Therefore the current state is updated with each operation timing, and the path metric P of the current state is also updated with each input timing. In an ideal situation (i.e. without noise), there must be an optimum path metric in the path metrics P of each current state. Based on the method of generating the branch cost mentioned above, the value of the optimum path metric is equal to zero. The path of the optimum path metric relates to correct encoded signals. However, if no path metrics are equal to zero, the input signal is affected by noise. As a result, the minimum path metric is determined to be the optimum path metric and then the encoded signal is determined in the same manner.
Please refer to FIG. 3. FIG. 3 is a schematic diagram of a related art path metric computing unit 10. As shown in FIG. 3, the path metric computing unit 10 comprises a plurality of adders 21, 23, a comparator 25, a multiplexer 27, and a register 29. Take the operation of the path metric PS7 and the path metric PS3 as an example in the following description. Firstly, the adder 21 adds a path metric PS7 of a previous state S7 to a corresponding branch cost BS7->S7, and the adder 23 adds a path metric PS3 of a previous state S3 to a corresponding branch cost BS3->S7. Secondly, the comparator 25 compares the output values of the adders 21, 23, and outputs a control signal Sc to the multiplexer 27 according to the comparison result. Thirdly, the multiplexer 27 selects the smaller of the two input values according to the control signal Sc to be the path metric PS7 of the current state S7. Since other path metric computing units have the same architecture as the architecture of the path metric computing unit 10, and they compute the path metrics in the same manner, a detailed description of other path metric computing units is omitted. However, the architectures of path metric computing units mentioned above are not appropriate when the input data transfer rate is huge. A related method for processing a lot of input data in an operation timing is to increase the complexity of the circuits of path metric computing units. Hence, the manufacturing cost and difficulties increase accordingly.